#include <bits/stdc++.h>

using namespace std;


/*
动态规划原始版本
*/
class Solution1 {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        int len=s.length();
        vector<int> dp(len+1,0);
        dp[0]=1;
        int ans=dp[0];
        for(int j=1;j<len;j++){
            int i=j-1;
            for(;i>=0 && s[i]!=s[j] ;i--);
            if(i<0){
                dp[j]=dp[j-1]+1;
            }else if(dp[j-1]<j-i){
                dp[j]=dp[j-1]+1;
            }else if(dp[j-1]>=j-i){
                dp[j]=j-i;
            }
            ans=max(ans,dp[j]);
        }
        
        
        return ans;
    }
};
/*
动态规划哈希表优化
*/
class Solution2 {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        int len=s.length();
        vector<int> hashtab(128,-1);
        vector<int> dp(len+1,0);
        dp[0]=1;
        int ans=dp[0];
        hashtab[s[0]]=0;
        for(int j=1;j<len;j++){
            int i=hashtab[s[j]];
            if(i<0){
                dp[j]=dp[j-1]+1;
            }else if(dp[j-1]<j-i){
                dp[j]=dp[j-1]+1;
            }else if(dp[j-1]>=j-i){
                dp[j]=j-i;
            }
            hashtab[s[j]]=j;
             ans=max(ans,dp[i]);
        }
        
        return ans;
    }
};
/*
动态规划哈希表优化,dp数组多余了，可以考虑删掉
删掉dp后，空间省了不少，时间也降低了
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        int len=s.length();
        vector<int> hashtab(128,-1);
        int last=1,now=1,ans=1;
        hashtab[s[0]]=0;
        for(int j=1;j<len;j++){
            int i=hashtab[s[j]];
            if(i<0){
                now=last+1;
            }else if(last<j-i){
                now=last+1;
            }else if(last>=j-i){
                now=j-i;
            }
            hashtab[s[j]]=j;
            ans=max(ans,now);
            last=now;
        }
        return ans;
    }
};
int main(){
    Solution s;
    cout << s.lengthOfLongestSubstring(" ") <<endl;



    return 0;
}